/*
 * Copyright (c) 2021
 * User:LENOVO
 * File:复原IP地址.java
 * Date:2021/02/18 14:16:18
 */

package org.bytedance.字符串;


import com.alibaba.fastjson.JSONObject;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
 * <p>
 * 有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 * <p>
 * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效的 IP 地址。
 * <p>
 * 输入：s = "25525511135"
 * 输出：["255.255.11.135","255.255.111.35"]
 */
public class 复原IP地址 {

    public static void main(String[] args) {
        复原IP地址 instance = new 复原IP地址();
        String[] inputs = new String[]{
                "25525511135",
                "0000",
                "1111",
                "010010",
                "101023"
        };
        for (String line : inputs) {
            instance.res.clear();
            List<String> strings = instance.restoreIpAddresses(line);
            System.out.println(JSONObject.toJSONString(strings));
        }

    }

    private List<String> res = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        if (s == null || s.length() < 4) return Collections.emptyList();
        Pattern pattern = Pattern.compile("^\\d{4,12}$");
        Matcher matcher = pattern.matcher(s);
        if (!matcher.find()) {
            return Collections.emptyList();
        }
        LinkedList<String> trace = new LinkedList<>();
        dfs(s, 0, 0, trace);
        return res;

    }

    // start 为当前读取到n个ip，cur为当前读取s的哪一位
    private void dfs(String s, int start, int cursor, LinkedList<String> trace) {
        if (start == 4 && cursor == s.length()) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 4; i++) {
                sb.append(".").append(trace.get(i));
            }
            res.add(sb.toString().substring(1));
            return;
        }
        // 当读取了4个ip但是s还没有遍历完，则直接返回
        if (start == 4 && cursor != s.length()) return;
        for (int i = cursor; i < cursor + 3 && i < s.length(); i++) {
            String temp = s.substring(cursor, i + 1); //读取ip
            if (Integer.valueOf(temp) <= 255) {
                trace.add(temp);
                dfs(s, start + 1, i + 1, trace);
                trace.removeLast();
            }
            if (temp.equals("0")) break;
        }
    }
}
